package cn.edu.njust.alg.leetcode;

import java.util.ArrayList;
import java.util.List;

import cn.edu.njust.utils.ListUtils;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_54_Spiral_Matrix {

	public static List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> list = new ArrayList<Integer>();
		if (matrix == null || matrix.length == 0) {
			return list;
		}
		boolean[][] visited = new boolean[matrix.length][matrix[0].length];
		list.add(matrix[0][0]);
		int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
		int count = 1;
		visited[0][0] = true;
		int turn = 0;
		int i = 0, j = 0;
		int max = matrix.length * matrix[0].length;
		int p, q;
		while (count < max) {
			p = i + dir[turn % 4][0];
			q = j + dir[turn % 4][1];
			if (p < 0 || q < 0 || p >= matrix.length || q >= matrix[0].length
					|| visited[p][q]) {
				turn++;
				continue;
			}
			list.add(matrix[p][q]);
			visited[p][q] = true;
			count++;
			i = p;
			j = q;
		}

		return list;
	}

	public static void main(String[] args) {
		int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
		List<Integer> list = spiralOrder(matrix);
		ListUtils.printList(list);
	}

}
